As is well known to persons skilled in the art, in “identifier-based” cryptographic (IBC) methods a public, cryptographically unconstrained, string is used in conjunction with a public key of a trusted authority to carry out tasks such as data encryption and signing. The complementary tasks, such as decryption and signature verification, require the involvement of the trusted authority to carry out a computation based on the public string and a private key that is related to its public data. In message-signing applications and frequently also in message encryption applications, the string serves to “identify” a party (the sender in signing applications, the intended recipient in encryption applications); this has given rise to the use of the label “identifier-based” or “identity-based” generally for these cryptographic methods. However, at least in certain encryption applications, the string may serve a different purpose to that of identifying the intended recipient and, indeed, may be an arbitrary string having no other purpose than to form the basis of the cryptographic processes. Accordingly, the use of the term “identity-based” or “identifier-based” herein in relation to cryptographic methods and systems is to be understood simply as implying that the methods and systems are based on the use of a cryptographically unconstrained string whether or not the string serves to identify the intended recipient. Furthermore, as used herein the term “string” is simply intended to imply an ordered series of bits whether derived from a character string, a serialized image bit map, a digitized sound signal, or any other data source.
The current most practical approach to building identifier-based cryptosystems uses bilinear pairings. A brief overview of pairings-based cryptography will next be given. In the present specification, G1 and G2 denote two algebraic groups of large prime order l in which the discrete logarithm problem is believed to be hard and for which there exists a non-degenerate computable bilinear map p, for example, a Tate pairing or Weil pairing. Note that G1 is a [l]-torsion subgroup of a larger algebraic group G0 and satisfies [l]P=O for all PεG1 where O is the identity element, l is a large prime, and l*cofactor=number of elements in G0. The group G2 is a subgroup of a multiplicative group of a finite field.
For the Weil pairing: the bilinear map p is expressed asp: G1×G1→G2.
The Tate pairing can be similarly expressed though it is possible for it to be of asymmetric form:p: G1×G0→G2 
Generally, the elements of the groups G0 and G1 are points on an elliptic curve (typically, though not necessarily, a supersingular elliptic curve); however, this is not necessarily the case.
For convenience, the examples given below assume the use of a symmetric bilinear map (p: G1×G1→G2) with the elements of G1 being points on an elliptic curve; however, these particularities, are not to be taken as limitations on the scope of the present invention.
As is well known to persons skilled in the art, for cryptographic purposes, modified forms of the Weil and Tate pairings are used that ensure p(P,P)≠1 where PεG1; however, for convenience, the pairings are referred to below simply by their usual names without labeling them as modified.
As the mapping between G1 and G2 is bilinear, exponents/multipliers can be moved around. For example if a, b, cεZ (where Z is the set of all integers) and P, QεG1 then
                              p          ⁢                                          ⁢                                    (                              aP                ,                bQ                            )                        c                          =                              p            ⁢                                                  ⁢                                          (                                  aP                  ,                  cQ                                )                            b                                =                                    p              ⁢                                                          ⁢                                                (                                      bP                    ,                    cQ                                    )                                a                                      =                          p              ⁢                                                          ⁢                                                (                                      bP                    ,                    aQ                                    )                                c                                                                            =                              p            ⁢                                                  ⁢                                          (                                  cP                  ,                  aQ                                )                            b                                =                                    p              ⁢                                                          ⁢                                                (                                      cP                    ,                    bQ                                    )                                a                                      =                          p              ⁢                                                          ⁢                                                (                                      abP                    ,                    Q                                    )                                c                                                                            =                              p            ⁢                                                  ⁢                          (                              abP                ,                cQ                            )                                =                                    p              ⁢                                                          ⁢                                                (                                      P                    ,                    abQ                                    )                                c                                      =                                          p                ⁢                                                                  ⁢                                  (                                      cP                    ,                    abQ                                    )                                            =              …                                                              =                              p            ⁢                                                  ⁢                          (                              abcP                ,                Q                            )                                =                                    p              ⁢                                                          ⁢                              (                                  P                  ,                  abcQ                                )                                      =                          p              ⁢                                                          ⁢                                                (                                      P                    ,                    Q                                    )                                abc                                                        
A normal public/private key pair can be defined for a trusted authority:                the private key is s                    where sεZl and                        the public key is (P, R)                    where P and R are respectively master and derived public elements with PεG1 and RεG1, P and R being related by R=sP                        
With the cooperation of the trusted authority, an identifier-based public key/private key pair <QID, SID> can be defined for a party with identity string ID where:QID,SIDεG1.SID=sQID QID=H1(ID)H1 is a hash: {0,1}*→G1 
Further background regarding Weil and Tate pairings and their cryptographic uses (such as for encryption and signing) can be found in the following references:                G. Frey, M. Müller, and H. Rück. The Tate pairing and the discrete logarithm applied to elliptic curve cryptosystems. IEEE Transactions on Information Theory, 45(5):1717-1719, 1999.        D. Boneh and M. Franklin. Identity based encryption from the Weil pairing. In Advances in Cryptology—CRYPTO 2001, LNCS 2139, pp. 213-229, Springer-Verlag, 2001.        
With regard to the latter reference, it may be noted that this reference describes both a fully secure encryption scheme using the Weil pairing and, as an aid to understanding this fully-secure scheme, a simpler scheme referred to as “BasicIdent” which is acknowledged not to be secure against a chosen ciphertext attack.
As already mentioned above, the present invention is concerned with signcryption cryptographic schemes. A “signcryption” primitive was proposed by Zheng in 1997 in the paper: “Digital Signcryption or How to Achieve Cost(Signature & Encryption)<<Cost(Signature)+Cost(Encryption).” Y. Zheng, in Advances in Cryptology—CRYPTO '97, volume 1294 of Lecture Notes in Computer Science, pages 165-179, Springer-Verlag, 1997. This paper also proposed a discrete logarithm based scheme.
Identity-based signcryption is signcryption that uses identity-based cryptographic algorithms. A number of identity-based signcryption schemes have been proposed such as described in the paper “Multipurpose Identity-Based Signcryption: A Swiss Army Knife for Identity-Based Cryptography” X. Boyen, in Advances in Cryptology—CRYPTO 2003, volume 2729 of Lecture Notes in Computer Science, pages 382-398, Springer-Verlag, 2003. This paper also proposes a security model for identity-based signcryption that is based on six algorithms SETUP, EXTRACT, ENCRYPT, DECRYPT and VERIFY. For convenience of describing the prior art and the preferred embodiments of the invention, a similar set of six algorithms is used herein and the functions of each of these algorithms will now be described with reference to FIG. 1 of the accompanying drawings; it should, however, be understood that the present invention is not intended to be limited to implementations using such a set of six algorithms.
In FIG. 1 the algorithms SETUP 20 and EXTRACT 21 are associated with a trusted authority, the algorithms SIGN 22 and ENCRYPT 23 with a party A, and the algorithms DECRYPT 24 and VERIFY 25 with a party B. The functions of these algorithms are as follows:                SETUP—On input of a security parameter k this algorithm produces a pair <params, s> where “params” are the global public parameters for the system and s is the master secret key. The public parameters “params” include a global public key R, a description of a finite message space M, a description of a finite signature space S, and a description of a finite ciphertext space C. It is assumed below that “params” are publicly known and are therefore not explicitly provided as input to the other algorithms.        EXTRACT—On input of an identity IDU and the master secret key s, this algorithm computes a secret key SU corresponding to IDU.        SIGN—On input of <m, SA>, this algorithm produces a signature σ on m under IDA and some ephemeral state data r.        ENCRYPT—On input of <SA, IDB, m, σ, r>, this algorithm produces a ciphertext c. This is the encryption under IDB's public key of m and of IDA's signature on m.        DECRYPT—on input of <c′, SB>, this algorithm produces (m′, IDA′, σ′) where m′ is a message and σ′ is a purported signature on m′ of party with identity IDA′.        VERIFY—On input of <m′, IDA′, σ′>, this algorithm outputs True if σ is the signature of the party represented by IDA on m, and it outputs False otherwise.        
The marking of a quantity with ′ (as in m′) is to indicate that its equivalence to the unmarked quantity has to be tested.
The above individual algorithms 20 to 25 have the following consistency requirement. If:(m,σ,r)←SIGN(m,SA)c←ENCRYPT(SA,IDB,m,σ,r)(m′,IDA′,σ′)←DECRYPT(c,SB)
Then the following must hold:IDA′=IDA m′=m True←VERIFY(m′,IDA′,σ′)
It should be noted that other ways of modelling identity-based signcryption exist; for example, the signing and encryption algorithms may be treated as a single signcryption algorithm as are the decryption and verification algorithms. However, the above-described model will be used in the present specification.
The implementation of a signcryption scheme using the above six algorithms is straight-forward:                a trusted authority first executes SETUP;        the trusted authority executes EXTRACT to provide party A with the latter's secret key SA;        party A executes SIGN to form a signature σ on a message m, and ENCRYPT to encrypt the message m together with the signature;        the trusted authority executes EXTRACT to provide party B with the latter's secret key SB;        party B executes DECRYPT to recover m′, σ′ and a sender identity, and then VERIFY to verify the signature.        
It will be appreciated that the execution of EXTRACT to provide SB can be carried out at any time before DECRYPT is run.
The specific identity-based signcryption scheme described in the above-referenced paper by Boyen is based on bilinear pairings with the algorithms being implemented as follows:
Setup
                Establish public parameters G1, G2, l, q and the following cryptographic hash functions:H1: {0,1}k1→G1 H2: {0,1}k0+n→Zl*H3: G2→{0,1}k0 H4: G2→Zl*H5: G1→{0,1}k1+n                     where:                            k0 is the number of bits required to represent an element of G1;                k1 is the number of bits required to represent an identity; and                n is the number of bits of a message to be signed and encrypted.                                                Choose P such that <P>=G1 that is, P is a generator for the cyclic group G1.        Choose s uniformly at random from Zl*.        Compute the global public key R←sP.Extract        
To extract the private key for user U with IDUε{0,1}k1:                compute the public key QU←H1(IDU)        compute the secret key SU←sQU Sign        
For user A with identity IDA to sign a message mε{0,1}n with private key SA corresponding to public key QA←H1(IDA):                choose r uniformly at random from Zl* and compute:X←rQA         compute:h←H2(X∥m)                    where ∥ indicates concatenationJ←(r+h)SA                         return r and the signature σ=<X, J>.Encrypt        
For user A with identity IDA to encrypt message m, using r and σ output by SIGN, for user B with identity IDB:                compute:QB←H1(IDB)w←p(SA,QB)t←H4(w)Y←tX u←wtr         compute:f=H3(u)⊕J v=H5(J)⊕(IDA∥m)        return the ciphertext c: <Y, f, v>.Decrypt        
For user B with identity IDB to decrypt ciphertext c′: <Y′, f′, v′> using SB←H1(IDB):                compute:u′←p(Y′,SB)J′←f′⊕H3(u′)        compute:H5(J′)⊕v′        to recover string: IDA′∥m′        compute:QA′←H1(IDA′)w′←p(QA′,SB)t′←H4(w′)X′←(t′)−1 Y         return the message m′, the signature σ′=<X′, J′>, and the identity IDA′ of the purported sender.Verify        
To verify that the signature σ′ on message m′ is that of user A where A has identity IDA:                compute:h′←H2(X′∥m′)        check whether:p(J′,P)=p(R,X′+h′QA′)        and, if so, return True, else return False.        
The foregoing signature algorithm SIGN is based on an efficient signature scheme proposed in the paper “An Identity-Based Signature from Gap Diffie-Hellman Groups” J. C. Cha and J. H. Cheon, in Public Key Cryptography—PKC 2003, volume 2567 of Lecture Notes in Computer Science, pages 18-30, Springer-Verlag, 2003.
Our co-pending U.S. patent application Ser. No. 10/977,342 filed Oct. 29, 2004 discloses an identity-based signcryption scheme that uses bilinear maps and provides improved efficiency. However, the signcryption scheme disclosed in that application involves the message sender and message receiver using the same trusted authority. In many practical applications, the message sender and message recipient will belong to different trusted-authority domains. Prior IBC solutions for such situations generally involve separate identity-based signature and encryption schemes with each scheme using the trusted authorities of both the message sender and receiver.
It is an object of the invention to provide a signcryption scheme where the message sender and message receiver belong to different trusted-authority domains.